#快速排序

def QuickSort(List):
    def _sort(List, first, last):
        if last > first:
            split = partition(List, first, last)
            _sort(List, first, split-1)
            _sort(List, split+1, last)
    _sort(List, 0, len(List)-1)

def partition(List, first, last):
    datum = List[first] #基准值

    if last-first > 3: #三数取中法：取前三个数的中值作为基准值。
        d1,d2 = List[first+1],List[first+2]
        d1,d2 = (d1,d2) if d1>d2 else (d2,d1)
        datum=min(d1,datum); datum=max(d2,datum)

    left = first+1
    right = last
    done = False
    while not done:
        while left <= right and List[left] <= datum:
            left += 1
        while List[right] >= datum and right >= left:
            right -= 1
        if right < left: done = True
        else: List[left],List[right] = List[right],List[left]
    List[first], List[right] = List[right], List[first]
    return right


# a=[7,8,6,9,5,3,0,3]
# QuickSort(a)
# print(a)

